NeurIPS 2020 | 可解释的投票

关键词：voting; explainability

导读

本文是第三十四届神经信息处理系统大会（NeurIPS 2020）入选论文《可解释的投票 （Explainable Voting）》的解读。

论文下载：https://zixinzhou.com/pdf/explain.pdf

（或点击文末“阅读原文”跳转）

投票在许多的场景中都是非常重要的， 比如政治选举，聚合专家意见，或者把多个机器学习模型整合到一起等。在之前的许多工作中，投票机制是自动决策系统中至关重要的一环，因此一个可以解释的投票系统就毫无疑问是通向可解释AI的基础。本文着重讨论了一个全新的投票机制解释模型，并给出了一套数学框架对其表现进行刻画。

具体来说，我们使用一些简单的公理来解释一个投票方法为什么对于一个给定的输入所产生的胜者会是某个候选人。以 Borda 这个性质非常好的投票方法为例，我们接下来要解释的投票输入有4个候选人，分别为 a, b, c, d。8个投票人，他们对这4个候选人的偏好分别是 (a, d, b, c); (b, a, c, d); (b, a, d, c); (b, d, c, a); (c, a, b, d); (c, a, d, b); (c, d, a, b); (d, a, c, b)。下图展示了我们的解释框架是如何进行的：

从这个例子出发，一般来说，我们的解释思路如下：

1. 将输入给分解成若干子输入。

2. 对于每个子输入，使用其于对称性和有效性的公理来得到相应的胜者。例如对于 (a, b, c); (b, a, c)，由于在这个输入中 a, b 的位置是对称的，且严格优于 c，因此可以得到这个子输入的胜者应该是 {a, b}。

3. 最后将所有子输入的胜者给合并起来，这里合并的途径是利用相容性公理。例如对于 (a, b, c) 和 (a, b, c); (b, a, c) 这两个子输入，由于前者的胜者是 {a}，后者的胜者是 {a, b}。我们可以得到 (a, b, c); (a, b, c); (b, a, c) 的胜者一定是 {a}（{a}和{a,b} 的交集）。

在这里提到的对称性、有效性公理和相容性公理是两个大类的公理。本文一大创新之处就是几类相似的公理给抽象出来。还是以 Borda 为例，我们使用了如下3个对称性、有效性公理：

1. ELEM: For each elementary profile  , the set of winners should be  , so  

2. CYCL: For each cyclic profile  , the set of winners should be all of  , so  

3. CANC: If for all  , the same number of voters prefer  to  as prefer  to  , then the set of winners is  . Formally, for all   with  for all  ,   

和4个相容性公理：

1. REINF: For any two profiles  and  , and any two subsets of alternatives  and  with  , it holds that  

2. REINF-SUB: Subtracting a profile with a full winner set does not change the outcome. Formally, for all  ,  ,   

3. SIMP: A profile that is a repetition of some sub-profile should have the same set of winners as the sub-profile. Formally, for each  ,   

4. MULT: If a profile  has winner set  , then the profile that repeats    times has the same winner set. Formally, for each  ,   

共7个公理来解释 Borda。可以看到其中每个公理都是很符合直观的（否则也就不能称之为公理了）。当然能够解释一个投票机制的公理可能有非常多的选择，为了把相似的公理都刻画出来，本文创新地将投票方法和公理嵌入到线性空间中：

Definition 1. A voting rule  can be embedded into a linear space  over  via  and  if the following properties are satisfied:

并提出了如下四个元公理（meta-axiom）：

1. ADD: For all  such that  ,  

2. EMB: For all  such that  ,  

3. INIT: For all  ,  

4. PRED: For all  and all  such that  ,  , where  is the kernel of  

之前提到的一些公理都是这4个元公理的特例。借助线性代数的工具，我们就可以描述一大类投票机制的公理解释了。

我们研究中遇到的一个挑战是：仅仅知道这样的解释的存在性是远远不够的，在实际应用中，我们想要的是越短越好的解释。本文证明了，Borda 可以用之前提到的7个公理生成一个  长度的解释，其中  是候选人的个数。

我们知道了一些解释长度的上界之后，一个很自然的问题就是，这些解释的长度下界是什么样的。本文的主要结果是一个一般性的下界：如果一个投票方法能嵌入到  维空间，并且公理能被上述4个元公理所刻画，那么是不可能找到比  更短的解释的。利用这个定理，我们得到了几个推论：

1. Borda 不能在  步数内被解释，结合上界，我们得到了 Borda 在7个公理下的解释长度为  。

2. Plurality 不能在  步数内被解释。

3. Approval 不能在  步数内被解释。

最后，值得一提的是我们下界不仅在最坏的情况下成立，它对于几乎所有的输入都成立。

总结：从一方面来说，我们希望我们的工作能够帮助投票机制的设计者更好地解释相应的机制，从另一方面来说，我们希望有关解释长度的探索能够指导未来实践中的投票方法和公理的选择——谁都不想看到一个投票结果需要很长很长的步数才能被解释。我们的理论在不同的应用中也许会有不同的意义，例如在政治选举中，因为候选者的个数不多，所以一个  的解释步数是完全可以接受的，相反，在 ensemble learning 和 virtual democracy 的例子中，候选方法可能非常非常多，因此一个  的解释可能是无法接受的。在这样的场景中，我们要下界就能帮助识别哪些是好的，可用的，哪些是不可用的投票与解释。

NeurIPS

神经信息处理系统大会（Conference on Neural Information Processing Systems, NeurIPS）是人工智能和机器学习领域的国际顶级会议，自1987年开始，每年的12月份，来自世界各地的从事人工智能和机器学习相关的专家学者和从业人士汇聚一堂。NeurIPS 2020将于12月6日-12日在线举行。

图文 | 周子鑫

近 期 科 研 动 态 

—   版权声明  —

本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。

点击“阅读原文”跳转论文